<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title> 堆排序 </title>
</head>
<body>
    <div>
        <img src="./堆结构.png" alt="">
    </div>
</body>
</html>
<script>
    //2021-06-08-白  
    //只有小孩子才问你为什么不理我，成年人都是心照不宣地相互疏远。但凡能说透的东西，基本也就是释怀了，要知道，心结，是说不清楚的，甚至说不出口。

    //堆排序是一种特殊的树 只有满足这俩点 他就是一个堆  
    /*  
        1 堆是一个完全的二叉树，
          完全二叉树 除了最后一层 其他层的节点个数都是满的 最后一层的节点靠左排列   
        2 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值 
          也可以说 堆中的每个节点的值都大于等于(或者小于等于) 其左右节点的值 这两个表述是等价的    
        3 对于每个节点的值都大于等于 子树中每个节点值的堆 我们叫作 大顶锥  
          对于每个节点的值都小于等于 子树中每个节点值的堆 我们叫做 小顶锥
    */ 

    //其中图 1 和 图 2 是大顶堆，图 3 是小顶堆，图 4 不是堆。除此之外，从图中还可以看出来，对于同一组数据，我们可以构建多种不同形态的堆。

    //思路  
    // 将初始待排序关键字序列 (R1, R2 .... Rn) 构建成大顶堆，此堆为初始的无序区；
    // 将堆顶元素 R[1] 与最后一个元素 R[n] 交换，此时得到新的无序区 (R1, R2, ..... Rn-1) 和新的有序区 (Rn) ，且满足 R[1, 2 ... n-1] <= R[n]。
    // 由于交换后新的堆顶 R[1] 可能违反堆的性质，因此需要对当前无序区 (R1, R2 ...... Rn-1) 调整为新堆，然后再次将 R[1] 
    // 与无序区最后一个元素交换，得到新的无序区 (R1, R2 .... Rn-2) 和新的有序区 (Rn-1, Rn)。
    // 不断重复此过程，直到有序区的元素个数为 n - 1，则整个排序过程完成。

    //代码示例 
    // 堆排序
const heapSort = array => {
	                                                               // console.time('堆排序耗时');
	for (let i = Math.floor(array.length / 2 - 1); i >= 0; i--) {  // 初始化大顶堆，从第一个非叶子结点开始
		heapify(array, i, array.length);
	}
	for (let i = Math.floor(array.length - 1); i > 0; i--) {       // 排序，每一次 for 循环找出一个当前最大值，数组长度减一
		swap(array, 0, i);                                           // 根节点与最后一个节点交换
		heapify(array, 0, i);                                        // 从根节点开始调整，并且最后一个结点已经为当前最大值，不需要再参与比较，所以第三个参数为 i，即比较到最后一个结点前一个即可
	}
	                                                               // console.timeEnd('堆排序耗时');
	return array;
};

// 交换两个节点
const swap = (array, i, j) => {
	let temp = array[i];
	array[i] = array[j];
	array[j] = temp;
};

// 将 i 结点以下的堆整理为大顶堆，注意这一步实现的基础实际上是：
// 假设结点 i 以下的子堆已经是一个大顶堆，heapify 函数实现的
// 功能是实际上是：找到 结点 i 在包括结点 i 的堆中的正确位置。
// 后面将写一个 for 循环，从第一个非叶子结点开始，对每一个非叶子结点
// 都执行 heapify 操作，所以就满足了结点 i 以下的子堆已经是一大顶堆

const heapify = (array, i, length) => {
	let temp = array[i]; // 当前父节点
	// j < length 的目的是对结点 i 以下的结点全部做顺序调整
	for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {
		temp = array[i]; // 将 array[i] 取出，整个过程相当于找到 array[i] 应处于的位置
		if (j + 1 < length && array[j] < array[j + 1]) {
			j++; // 找到两个孩子中较大的一个，再与父节点比较
		}
		if (temp < array[j]) {
			swap(array, i, j); // 如果父节点小于子节点:交换；否则跳出
			i = j; // 交换后，temp 的下标变为 j
		} else {
			break;
		}
	}
};
const array = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
console.log('原始array:', array);

const newArr = heapSort(array);
console.log('newArr:', newArr);
                                    //123456789



                                    // https://juejin.cn/post/6844903895789993997#heading-3  博客 
    



</script>